package dp.countBits;
/**
 * @Date 2020/04/18
 * @author 王光浩
 * @Thinking 使用DP
 * 		如果一个数是奇数：前一个数的 1 的个数 +1
 * 		如果一个数是偶数：1 的个数 和 这个偶数除以2 之后数的 1 的个数相同。
 * 
 */
public class MyMethodTwo {
	public int[] countBits(int num) {
		int[] ret = new int[num+1];
		for(int i=1 ; i<=num ; i++) {
			if( (i&1)==1 ) {
				//奇数
				ret[i] = ret[i]+1;
			}
			else {
				//偶数
				ret[i] = ret[i/2];
			}
		}
		return ret;
	}
	public int[] countBits1(int num) {
		int[] ret = new int[num+1];
		for(int i=1 ; i<=num ; i++) {
			ret[i] = ret[i&(i-1)]+1;
		}
		return ret;
	}
	
}
